package test;

import com.alibaba.fastjson2.JSON;
import com.alibaba.fastjson2.JSONArray;

import java.util.HashSet;
import java.util.Set;

/**
 * @author sunzhuokun
 * @date 10:24 2024/5/16
 * @description 服务器广播
 * 服务器连接方式包括直接相连，间接连接。
 * A 和 B 直接连接， B 和 C 直接连接，则 A 和 C 间接连接。直接连接和间接连接都可以发送广播。
 * 给出一个 N * N 数组，代表 N 个服务器， matrix[i][j] == 1 ，则代表 i 和 j 直接连接；
 * 不等于 1 时，代表 i 和 j 不直接连接。 matrix[i][i]== 1 ，即自己和自己直接连接。
 * matrix[i][j]==matrix[j][i] 。
 * 计算初始需要给几台服务器广播，才可以使侮个服务器都收到广播。
 * <p>
 * 【分析】
 * 实质是图的遍历，求连通分量的个数；
 * 做这道题的时候没想到遍历该怎么写，用了比较麻烦的方法；
 * 用一个 Set 存储一个连通分量，将它们保存到数组中，数组的长度就是连通分量的个数，即本题的答案；
 * 具体做法是：遍历整个邻接矩阵，每遍历到新的一行，判断当前节点是否已经存在于某个已有的连通分量，如果有，将与其直接连接的节点存到该连通分量；如果没有，新建一个 Set （新连通分量）进行存储，最后得到整个连通分量的数组，用 Set
 * 是保证没有重复
 */
public class ServerBroadcast_服务器广播 {

    public static void main(String[] args) {
        String input = "[[1,0,1,0,1,1],[0,1,0,0,0,0],[1,0,1,0,0,0],[0,0,0,1,0,0],[1,0,0,0,1,0],[1,0,0,0,0,1]]";
        JSONArray arr = JSON.parseArray(input);
        int len = arr.size();
        Set<Set<Integer>> res = new HashSet<>();

        for (int i = 0; i < len; i++) {
            // 标记：判断当前节点是否已经被记录（已属于已有的某个连通分量）
            boolean flag = false;

            // 当前所指向的连通分量
            Set<Integer> temp = null;

            for (Set<Integer> x : res) {
                if (x.contains(i)) {
                    // 若在连通分量数组中找到，表示该节点已经与之前的节点连通，那么与该节点连通的节点，也与之前的节点间接连通
                    temp = x;
                    flag = true;
                    break;
                }
            }

            if (!flag) {
                // 如果未找到，则创建一个新的set：表示一个新的连通分量
                Set<Integer> set = new HashSet<>();
                set.add(i);
                res.add(set);
                temp = set;
            }

            for (int j = i + 1; j < len; j++) {
                // 邻接矩阵对称，所以从 i+1 开始
                if (Integer.parseInt(((JSONArray) arr.get(i)).get(j).toString()) == 1) {
                    // i 与 j 直接连通，将 j 存储到 i 所属的连通分量中
                    temp.add(j);
                }
            }
        }

        System.out.println(res.size());
    }
}
